package com.pandy.code;

/**
 * 异或运算
 *
 * 异或运算：相同为0，不同为1 （无进位相加）
 * 同或运算：相同为1，不同为0
 *
 * 0 ^ N = N
 * N ^ N = 0
 * 异或运算满足交换律和结合律  a^b^c^d = d^c^b^a
 */
public class Code03_XOR {

    /**
     * 如何不用额外变量交换两个数
     * @param a
     * @param b
     */
    public static void swap(int[] arr,int a, int b) {
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }

    /**
     * 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
     *
     * 思路：使用异或运算的交换律和结合律 偶数次数^等于0 ，0 ^ N = N
     * @param arr
     * @return
     */
    public static int printOddNumberValue(int[] arr) {
        int eor = 0;
        for(int i=0; i<arr.length; i++) {
            eor ^= arr[i];
        }
        return eor;
    }

    /**
     * 怎么把一个int类型的数，提取出最右侧的1来
     * @param num
     * @return
     */
    public static int getRightMost1(int num) {
        return num & (-num); // num & (~num + 1)
    }

    /**
     * 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
     * @param arr
     * @return
     */
    public static int[]  printOddNumberValue2(int[] arr) {
        int[] result = new int[2];
        int eor = 0;
        // 这里操作完 eor = a ^ b
        for(int i=0; i<arr.length; i++) {
            eor ^= arr[i];
        }

        // 因为eor = a ^ b，肯定是有某一位是为1的，那提取出最右侧的1来（N位）
        int newValue = eor & (-eor);
        int eor1 = 0;
        // 这里数组中肯定是两类数，一类是N位是1的，一个是N位是0的（a,b两个数肯定也是分别在这两类中）
        for(int i=0; i<arr.length; i++) {
            // eor1只和N位是1的的进行异或，找出其中一个数a
            if((arr[i] & newValue) != 0) {
                eor1 ^= arr[i];
            }
        }
        result[0] = eor1; //a
        result[1] = eor ^ eor1; // a ^ b ^ a = b

        return result;
    }

    public static void print(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        int[] arr = {1,2,3,4,5,6,7};
//        print(arr);
//        swap(arr, 3, 4);
//        print(arr);

//        int[] arr = {3,1,5,1,1,7,1,1,7,1,3,5,3,3,5};
//        System.out.println(printOddNumberValue(arr));

//        int num = 8;
//        System.out.println(getRightMost1(num));

        int[] arr = {3,1,5,1,1,7,1,9,1,7,1,3,5,3,3,5};
        print(printOddNumberValue2(arr));
    }
}
